#include <iostream>

/*
Suppose we have an array a1,a2,.....,an,b1,b2, ......bn.  
How to change this array to a1,b1,a2,b2......an,bn in O(n) time 
without using any space.

the following solution is for O(nlgn) time complexity. 
For the O(n) time, refer http://blog.csdn.net/yuan8080/article/details/5705567 
for perfect shuffle solution.
*/
using namespace std;

void RevertString( char *arr, int left, int right)
{
	while( left<right)
	{
		char temp = arr[left];
		arr[left] = arr[right];
		arr[right] = temp;
		left++;
		right--;
	}
}

void ShuffleString( char* arr, int left, int mid, int right)
{
	RevertString( arr, left, mid-1);
	RevertString( arr, mid, right);
	RevertString( arr, left, right);
}

void ReShuffle(char *arr, int left, int right)
{
	if( right < left+1 || (right-left+1)%2 )
		throw;

	int len = (right-left+1)/2;
	if( len == 1)
	{
		//only 1 left, finish the shuffle and return
		return;
	}

	int lenLeft = len/2;
	int lenRight = len - lenLeft;

	ShuffleString( arr, left+lenLeft, left+len, left+len+lenLeft-1);
	ReShuffle( arr, left, left+lenLeft*2-1);
	ReShuffle( arr, left+lenLeft*2, right);
	return;
}

int main(void)
{
	char str[]="1234567abcdefg";
	cout<<"original string:"<<str<<endl;

	int len = strlen(str);

	ReShuffle(str, 0, len-1);

	cout<<"after convert:"<<str<<endl;

	cout<<"press any key to terminate"<<endl;
	return getchar();
}
